MacHack 1998/MacHack 1998.toast/Programming Contest/~Solutions Submitted/Problem 02 - Hearn/Solution.cp

Text File | 1998-06-19 | 4.9 KB | 280 lines | [TEXT/CWIE]

/*
Problem 02 - Hower of Tanoi

This problem is to solve a variant of the Tower of Hanoi puzzle.  You remember
the Tower of Hanoi, a board with three pegs, one of which has N disks of size
1, 2, 3, ... N, with the smallest disk at the top.  In the standard puzzle, the
goal is to move all of the disks from one peg to another peg, by repeatedly
moving a disk from the top of one peg to another peg without ever placing a
larger disk on top of a smaller disk.

In our Hower of Tanoi problem, the objective and the constraints are the same,
except that the disks on the first peg are initially in random order. You can
still only move a smaller disk onto a larger disk.

Your objective is output the moves required to place all the disks on peg 3 in
order with the smallest disk at the top.

Input specification

The first line of the input file contains an integer M, M<1000, the number of
disks in the problem.  The next M lines contain the numbers 1 .. M, one number
per line, randomly ordered, where the first number is the size of the top disk
on peg 1, the second number is the size of the 2nd disk from the top, etc.

Output specification

The output is a sequence of lines, each representing a single move,  consisting
of the source peg number followed by a comma (',') followed by the destination
peg number, followed by a return character.

Sample input

2
2
1

Sample output

1,3
1,3
*/

#include "Solution.h"

#include <stdio.h>
#include <stdlib.h>

// Fill in your solution and then submit this folder

// Team Name: Bob Hearn

long Disks;

#define MAXDISKS    1000

struct Towers
{
    int tower[3][MAXDISKS];
    int top[3];
};

Towers TheTowers;

struct Move
{
    short from, to;
};

const long MaxMoves = 10000;

struct Move Moves[MaxMoves];
long NumMoves;

long GetNumber(short rn);

long GetNumber(short rn)
{
long size = 1;
char c;
long number = 0;
OSErr err;

    while (1)
    {
        err = FSRead(rn, &size, &c);

        if (err || c == '\r')
            break;

        number *= 10;
        number += c - '0';
    }

    return number;
}

void WriteNumber(short rn, long num);
void WriteChar(short rn, char c);

void WriteNumber(short rn, long num)
{
    if (num > 9)
        WriteNumber(rn, num / 10);

    WriteChar(rn, num + '0');
}

void WriteChar(short rn, char c)
{
long size = 1;

        FSWrite( rn, &size, &c );
}


short Find(long disk);
short GoodState(long disk);
short Almost(long disk);
short Top(short tower);
void DoMove(short from, short to);
void RandMove();

pascal OSErr HowerOfTanoi( const FSSpec* infile, const FSSpec* outfile )
{
short rn;
OSErr err;
long x;
short tower;

    srand(TickCount());

    err = FSpOpenDF( infile, fsRdPerm, &rn );

    Disks = GetNumber(rn);

    for (x = 0; x < Disks; ++x)
        TheTowers.tower[0][Disks - x - 1] = GetNumber(rn);

    TheTowers.top[0] = Disks;
    TheTowers.top[1] = 0;
    TheTowers.top[2] = 0;

    FSClose(rn);

    NumMoves = 0;

    for (x = Disks; x > 0; --x)
    {
        tower = Find(x);
        DoMove(tower, 3);
    }

    err = FSpCreate( outfile, 'CWIE', 'TEXT', 0 );
    err = FSpOpenDF( outfile, fsWrPerm, &rn );

    for (x = 0; x < NumMoves; ++x)
    {
        WriteNumber(rn, Moves[x].from);
        WriteChar(rn, ',');
        WriteNumber(rn, Moves[x].to);
        WriteChar(rn, '\r');
//        fprintf(rn, "%d,%d\n", Moves[x].from, Moves[x].to);
    }

    FSClose(rn);

    return noErr;
}

Towers OldTowers;

short Find(long disk)
{
long oldmoves = NumMoves;
long x, y;
short tower;
long max = 100;

    OldTowers = TheTowers;

    while (++max)
    {
        for (x = 0; x < max; ++x)
        {
            if (tower = GoodState(disk))
                return tower;

        //    if (tower = Almost(disk))
        //    {
        //        DoMove(tower, 3 - tower);
        //
        //        return tower;
        //    }

            RandMove();
        }

    //    TheTowers = OldTowers;

        for (x = 0; x < 3; ++x)
        {
            TheTowers.top[x] = OldTowers.top[x];
            for (y = 0; y < TheTowers.top[x]; ++y)
                TheTowers.tower[x][y] = OldTowers.tower[x][y];
        }

        NumMoves = oldmoves;

//        printf("\nPop to move %d\n\n", NumMoves);
    }

    return tower;
}

short GoodState(long disk)
{
    if (Top(3) == disk + 1)
    {
        if (Top(1) == disk)
            return 1;
        if (Top(2) == disk)
            return 2;
    }

    return 0;
}

short Almost(long disk)
{
    if (Top(3) == disk + 1)
    {
        if (Top(1) > Top(2))
        {
            if (TheTowers.top[1] > 1 && TheTowers.tower[1][TheTowers.top[1] - 2] == disk)
                return 2;
        }
        else
        {
            if (TheTowers.top[0] > 1 && TheTowers.tower[0][TheTowers.top[0] - 2] == disk)
                return 1;
        }
    }

    return 0;
}

void DoMove(short from, short to)
{
//    printf("%d: move %d to %d\n", NumMoves, from, to);

    TheTowers.tower[to - 1][TheTowers.top[to - 1]++] = TheTowers.tower[from - 1][--TheTowers.top[from - 1]];
    Moves[NumMoves].from = from;
    Moves[NumMoves++].to = to;
}

short Top(short tower)
{
    if (TheTowers.top[tower - 1])
        return TheTowers.tower[tower - 1][TheTowers.top[tower - 1] - 1];

    return Disks + 1;
}

void RandMove()
{
short from, to;

    while (1)
    {
        from = (((unsigned) rand()) % 3) + 1;
        to = (((unsigned) rand()) % 3) + 1;

        if (TheTowers.top[from - 1] && Top(to) > Top(from))
        {
            DoMove(from, to);
            return;
        }
    }
}